package tree;

/**
 * @Author leecho
 * @Date: 2021/10/25 9:31
 * @Version 1.0
 */

public class BinaryTreeDemo {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1, "AA");
        BinaryTree binaryTree = new BinaryTree(node);

        TreeNode node1 = new TreeNode(2, "BB");
        TreeNode node2 = new TreeNode(3, "CC");
        TreeNode node3 = new TreeNode(4, "DD");
        TreeNode node4 = new TreeNode(5, "EE");

        node.setLeft(node1);
        node.setRight(node2);
        node2.setRight(node3);
        node2.setLeft(node4);

        binaryTree.inFixListBinaryTree();
        System.out.println();
        binaryTree.perListBinaryTree();
        System.out.println();
        binaryTree.sufFixListBinaryTree();
        System.out.println();

        System.out.println("===========");

        TreeNode resNode = binaryTree.perSearchBinaryTree(1);
        if (resNode == null)
            System.out.println("没有找到该编号的节点");
        else
            System.out.println("有该编号的节点，它的名字是："+resNode.getName());

    }

}

/*
* 思路
* - 创建一个结点类
* - 采用递归的方法来遍历查找和删除
* */
class BinaryTree{
    private TreeNode head;

    public BinaryTree(TreeNode head) {
        this.head = head;
    }

    public void perListBinaryTree(){
        if (head == null)
            System.out.println("为空无法遍历");
        else
            this.head.perList();
    }

    public void inFixListBinaryTree(){
        if (head == null)
            System.out.println("为空无法遍历");
        else
            this.head.inFixList();
    }

    public void sufFixListBinaryTree(){
        if (head == null)
            System.out.println("为空无法遍历");
        else
            this.head.sufFixList();
    }

    public TreeNode perSearchBinaryTree(int no){
        if (head == null)
            return null;
        else
           return this.head.perSearch(no);
    }

    public TreeNode inFixSearchBinaryTree(int no){
        if (head == null)
            return null;
        else
            return this.head.inFixSearch(no);
    }

    public TreeNode sufFixSearchBinaryTree(int no){
        if (head == null)
            return null;
        else
            return this.head.sufFixSearch(no);
    }

    public void delNodeBinaryTree(int no){
        if (head != null){
            if (head.getNo() == no){
                head = null;
            }else {
                head.deleteNode(no);
            }
        }else {
            System.out.println("该树为空，无法进行删除");
        }
    }

}

class TreeNode{
    private int no;
    private String name;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public void perList(){
        System.out.println(this.toString());
        if (this.left != null){
            this.left.perList();
        }
        if (this.right != null){
            this.right.perList();
        }
    }

    public void inFixList(){
        if (this.left != null){
            this.left.inFixList();
        }
        System.out.println(this.toString());
        if (this.right != null){
            this.right.inFixList();
        }
    }

    public void sufFixList(){
        if (this.left != null){
            this.left.sufFixList();
        }
        if (this.right != null){
            this.right.sufFixList();
        }
        System.out.println(this.toString());
    }


    public TreeNode perSearch(int no){
        if (this.no == no)
            return this;
        TreeNode res = null;
        if (this.left != null){
            res = this.left.perSearch(no);
        }
        if (this.right != null){
            res = this.right.perSearch(no);
        }
        return res;
    }

    public TreeNode inFixSearch(int no){
        TreeNode res = null;
        if (this.left != null){
            res = this.left.perSearch(no);
        }
        if (this.no == no)
            return this;
        if (this.right != null){
            res = this.right.perSearch(no);
        }
        return res;
    }

    public TreeNode sufFixSearch(int no){
        TreeNode res = null;
        if (this.left != null){
            res = this.left.perSearch(no);
        }
        if (this.right != null){
            res = this.right.perSearch(no);
        }
        if (this.no == no)
            return this;
        return res;
    }

    public void deleteNode(int no){
        if (this.left != null && this.left.getNo() == no){
            this.left = null;
            return;
        }
        if (this.right != null && this.right.getNo() == no){
            this.right = null;
            return;
        }
        if (this.left != null){
            this.left.deleteNode(no);
        }
        if (this.right != null){
            this.right.deleteNode(no);
        }

    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}